package leetcode_401_500;

import node.TreeNode;

import java.lang.annotation.Target;

public class LeeCode_437 {
    public static void main(String[] args) {
        System.out.println(pathSum(new TreeNode(1, new TreeNode(2, new TreeNode(3, new TreeNode(4), null), null), null),
                3));
    }
    private static int pathSum(TreeNode root, int targetSum) {
        long[] ans = new long[1];
        dfs1(root, ans, targetSum);
        return (int) ans[0];
    }
    private static void dfs1(TreeNode node, long[] ans, long target){
       if (node == null)
           return;
       dfs2(node, 0, target, ans);
       dfs1(node.left, ans, target);
       dfs1(node.right, ans, target);
    }
    private static void dfs2(TreeNode node, long sum, long target, long[] ans){
        if (node == null)
            return;
        long news = sum + node.val;
        if (news == target){
            ans[0]++;
        }
        dfs2(node.left, news, target, ans);
        dfs2(node.right, news, target, ans);
    }
}
